package com.example.leetcode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 单调栈 & 双指针 & 动态规划
 * 接雨水
 */
public class Demo0042 {

    public static void main(String[] args) {
        int[] height=new int[]{0,1,0,2,1,0,1,3,2,1,2,1};
        trap(height);
    }

    //方案一
    public static int trap(int[] height) {
        int ans=0;
        Deque<Integer> stack=new ArrayDeque<>();
        int len = height.length;
        for (int i = 0; i <len ; i++) {
            int curHigh = height[i];
            //1.考虑出栈
            while (!stack.isEmpty() && height[stack.peekLast()]< curHigh){
                //2.出完栈判空
                Integer lower = stack.pollLast();
                if (stack.isEmpty()){
                    break;
                }
                //3.判空后栈中必然有元素
                int left=stack.peekLast();
                //4.有元素可能有水，无需担心高度一样(会获得结果0)
                ans+=(i-left-1)*(Math.min(curHigh,height[left])-height[lower]);
            }

            //5.不出栈则入栈
            stack.addLast(i);
        }
        //不出栈则无水储存

        return ans;
    }

    /**
     * dp解法
     * 两次循环 leftMax[i] rightMax[i] ,然后求每个f[i]
     */
    public static int trap1(int[] height){
        int len=height.length;
        int[] left=new int[len];
        int[] right=new int[len];
        left[0]=0;
        right[len-1]=0;
        for (int i = 1; i < len; i++) {
            left[i]=Math.max(left[i-1],height[i-1]);
            right[len-1-i]=Math.max(right[len-i],height[len-i]);
        }
        int ans=0;
        for (int i = 0; i < len; i++) {
            if (Math.min(left[i],right[i])>height[i]){
                ans+=Math.min(left[i],right[i])-height[i];
            }
        }
        return ans;
    }
}
